A disk array or RAID (Redundant Array of Inexpensive Disks) storage system comprises two or more hard disk drives, such as the commodity 31/2 inch disk drives currently used in personal computers and workstations, functioning together as a single storage system. Although disk array products have been available for several years, significant improvements in the reliability and performance of small disk drives and a decline in the cost of such drives, together with end user requirements for increased system storage capacity, faster access speeds, improved reliability, and greater resistance to errors have resulted in enhanced interest in RAID systems.
Several disk array design alternatives were first described in an article titled "A Case for Redundant Arrays of Inexpensive Disks (RAID)" by David A. Patterson, Garth Gibson and Randy H. Katz; University of California Report No. UCB/CSD 87/391, December 1987. This article discusses disk arrays and the improvements in performance, reliability, power consumption and scalability that disk arrays provide in comparison to single large magnetic disks. Five disk array arrangements, referred to as RAID levels, are described. The simplest array, a RAID level 1 system, comprises one or more disks for storing data and an equal number of additional "mirror" disks for storing copies of the information written to the data disks. The remaining RAID levels, identified as RAID level 2, 3, 4 and 5 systems, segment the data into portions for storage across several data disks. One or more additional disks are utilized to store error check or parity information.
In 1993, these RAID levels were formalized in the first edition of the RAIDBook, published by the RAID Advisory Board, an association of manufacturers and consumers of disk array storage systems. In addition to the five RAID levels described by Patterson et al., the RAID Advisory Board now recognizes four additional RAID levels, including RAID level 0, RAID level 6, RAID level 10 and RAID level 53.
In order to coordinate the operation of the multitude of disk or tape drives within an array to perform read and write functions, parity generation and checking, and data restoration and reconstruction, complex storage management techniques are required. Array operation can be managed through software routines executed by the host computer system, i.e., a software array architecture, or by a dedicated hardware controller constructed to control array operations.
A RAID level 4 disk array is comprised of N+1 disks wherein N disks are used to store data, and the additional disk is utilized to store parity information. Data to be saved is divided into portions consisting of one or many blocks of data for storage among the disks. The corresponding parity information, which can be calculated by performing a bit-wise exclusive-OR of corresponding portions of the data stored across the N data drives, is written to the dedicated parity disk. The parity disk is used to reconstruct information in the event of a disk failure. Writes typically require access to two disks, i.e., one of the N data disks and the parity disk, as will be discussed in greater detail below. Read operations typically need only access a single one of the N data disks, unless the data to be read exceeds the block length stored on each disk.
A RAID level 4 system including five data and parity disk drives, DRIVE A through DRIVE E is illustrated in FIG. 1. An array controller, not shown, coordinates the transfer of data between a host system and the array disk drives. The controller also calculates and checks parity information. Data blocks A0 through D4 and parity blocks P0 through P4 illustrate the manner in which data and parity is stored on the five array drives. Data blocks A0 through D4 are also identified as blocks 0 through 19.
RAID level 5 disk arrays are similar to RAID level 4 systems except that parity information, in addition to the data, is distributed across the N+1 disks in each group. Each one of the N+1 disks within the array includes some blocks for storing data and some blocks for storing parity information. Where parity information is stored is controlled by an algorithm implemented by the user. As in RAID level 4 systems, RAID level 5 writes typically require access to two disks; however, no longer does every write to the array require access to the same dedicated parity disk, as in RAID level 4 systems. This feature provides the opportunity to perform concurrent write operations.
A RAID level 5 system including five data and parity disk drives, DRIVE A through DRIVE E is illustrated in FIG. 3. An array controller, not shown, coordinates the transfer of data between a host system and the array disk drives. The controller also calculates and checks parity information. Data blocks A0 through E4 and parity blocks P0 through P4 illustrate the manner in which data and parity is stored on the five array drives. Data blocks A0 through E4 are also identified as blocks 0 through 19.
The relationship between the parity and data blocks in both the RAID level 4 and 5 systems described above, and illustrated in FIGS. 1 and 3, respectively, is as follows:
PARITY P0=(BLOCK 0).sym.(BLOCK 1).sym.(BLOCK 2).sym.(BLOCK 3) PA0 PARITY P1=(BLOCK 4).sym.(BLOCK 5).sym.(BLOCK 6).sym.(BLOCK 7) PA0 PARITY P2=(BLOCK 8).sym.(BLOCK 9).sym.(BLOCK 10).sym.(BLOCK 11) PA0 PARITY P3=(BLOCK 12).sym.(BLOCK 13).sym.(BLOCK 14).sym.(BLOCK 15)
As shown above, parity data can be calculated by performing a bit-wise exclusive-OR of corresponding portions of the data stored across the N data drives. However, because each parity bit is simply the exclusive-OR product of all the corresponding data bits from the data drives, new parity can be more easily determined from the old data and the old parity as well as the new data in accordance with the following equation: EQU new parity=old data.sym.new data.sym.old parity.
Although the parity calculation for RAID levels 4 or 5 shown in the above equation is much simpler than performing a bit-wise exclusive-OR of corresponding portions of the data stored across all of the data drives, a typical RAID level 4 or 5 write operation will require a minimum of two disk reads and two disk writes, in addition to the step of calculating the new parity information. This operation is referred to as a read-modify-write (RMW) operation. More than two disk reads and writes are required for data write operations involving more than one data block. Each individual disk read operation involves a seek and rotation to the appropriate disk track and sector to be read. The seek time for all disks is therefore the maximum of the seek times of each disk. A RAID level 4 or 5 system thus carries a significant write penalty when compared with a single disk storage device or with RAID level 1, 2 or 3 systems.
In addition to the advantages described above for RAID storage systems, i.e., increased system storage capacity, faster access speeds, improved reliability, RAID level 4 and 5 disk array systems also provide for concurrent read and write operations. These storage arrangements provide an increased transfer bandwidth for multiple block read and write operations, e.g., four consecutive blocks can be read or written concurrently, and also improves the performance of small transfer operations by allowing blocks residing on separate disk drives to be accessed in parallel.
An improved method for generating and maintaining parity information in a RAID level 4 or 5 system which reduces or eliminates the write penalty resulting from the manner in which parity information is traditionally calculated and maintained is desired.